#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

 //Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};
 
class Solution1 {
public:
    ListNode* partition(ListNode* head, int x) {
        if (!head) return head;
        ListNode* cur = head->next;
        ListNode* prev = head;
        ListNode* first_x = nullptr;
        while (cur)
        {
            if (first_x == nullptr && cur->val == x)
                first_x = cur;

            if (cur->val < x)
            {
                prev->next = cur;
                prev = cur;
                cur = cur->next;
                prev->next = first_x;
                continue;
            }
            cur = cur->next;
        }
        return head;
    }
};

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* cur = head;
        size_t n = 0;
        size_t len = 0;
        while (cur)
        {
            len++;
            if (cur->val == x) n++;
            cur = cur->next;
        }
        len -= n;
        int tmp = len;
        ListNode* last = head;
        while (tmp--)
            last = last->next;

        cur = head;
        while (cur&& len--)
        {
            if (cur->val == x)
            {
                swap(last->val, cur->val);
                /*int tmp = cur->val;
                cur->val = last->val;
                last->val = tmp;*/
                last = last->next;
            }
            cur = cur->next;
        }
        return head;
    }
};

int main()
{
    ListNode* head = new ListNode(1);
    head->next = new ListNode(4);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(2);
    head->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next = new ListNode(2);

    Solution().partition(head, 3);
}